import heapq
from typing import List


class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        inf = float(0)
        m = len(dungeon)
        n = len(dungeon[0])
        def f(val):
            heap = [(-val - dungeon[0][0], (0, 0))]
            distance = [[0 for _ in range(n)] for _ in range(m)]
            distance[0][0] = val + dungeon[0][0]
            while heap:
                cost,(x,y) = heapq.heappop(heap)
                cost = -cost
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    if nx < 0 or nx >= m: continue
                    if ny < 0 or ny >= n: continue
                    if cost + dungeon[nx][ny] <= 0: continue
                    if distance[nx][ny] >= cost + dungeon[nx][ny]: continue
                    distance[nx][ny] = cost + dungeon[nx][ny]
                    heapq.heappush(heap, (-distance[nx][ny],(nx,ny)))
            return distance[m-1][n-1] >= 1
        l = 0
        r = 1000 * m * n + 1
        while l <= r:
            mid = (l + r) >> 1
            if f(mid):
                r = mid - 1
            else:
                l = mid + 1
        return r + 1


if __name__ == '__main__':
    s = Solution()
    r = s.calculateMinimumHP( [[-2,-3,3],[-5,-10,1],[10,30,-5]])
    print(r)